package java_thinking.unit_17;

import java.util.ArrayList;
import java.util.List;

/**
 * @Desc:
 *      1.算法时间复杂度的表示法O(n²)、O(n)、O(1)、O(nlogn)
 *          1.1简单理解： 就是变量为n的时候，算法需要对变量操作次数的量级
 *          1.2例子：要找到一个数组里面最大的一个数，你要把n个变量都扫描一遍，操作次数为n，那么算法复杂度是O(n).
 *              用冒泡排序排一个数组，对于n个变量的数组，需要交换变量位置n^2 次，那么算法复杂度就是O(n^2 ).
 *              有时候，如果对变量操作的次数是个多项式比如n^4+n^2+n, 就取数量级最大的那个，O(n^4)
 *      2.面试必看： https://blog.csdn.net/zxt0601/article/details/77281231
 *                  https://blog.csdn.net/u013970971/article/details/78673480
 *
 *      3.由于 ArrayList 不是同步的，所以在并发访问时，如果在迭代的同时有其他线程修改了 ArrayList, fail-fast 的迭代器
 *       Iterator/ListIterator 会报 ConcurrentModificationException 错。因此我们在并发环境下需要外部给 ArrayList 加个同步锁
 *       ，或者直接在初始化时用 Collections.synchronizedList 方法进行包装：
 *       List list = Collections.synchronizedList(new ArrayList(...));
 *
 *      4.ArrayList 删除和添加慢的原因：在添加或删除的时候会使用System.arraycopy(浅复制)来对元素进行整体移位这样的操作，这相对较耗资源；
 *       在频繁的插入或者是删除元素的情况下
 *
 *      5.数组和链表的特性差异，本质是：连续空间存储和非连续空间存储的差异，主要有下面两点：     
 *          5.1ArrayList：底层是Object数组实现的：由于数组的地址是连续的，数组支持O(1)随机访问；数组在初始化时需要指定容量；数组
 *           不支持动态扩容，像ArrayList、Vector和Stack使用的时候看似不用考虑容量问题（因为可以一直往里面存放数据）；但是它们
 *           的底层实际做了扩容；数组扩容代价比较大，需要开辟一个新数组将数据拷贝进去，数组扩容效率低；适合读数据较多的场合
 *          5.2LinkedList：底层使用一个Node数据结构，有前后两个指针，双向链表实现的。相对数组，链表插入效率较高，只需要更改前后
 *           两个指针即可；另外链表不存在扩容问题，因为链表不要求存储空间连续，每次插入数据都只是改变last指针；另外，链表所需要
 *           的内存比数组要多，因为他要维护前后两个指针；它适合删除，插入较多的场景。另外，LinkedList还实现了Deque接口
 *
 *     6.Vector & ArrayList
 *          相同点：
 *              1、ArrayList和Vector都是继承了相同的父类和实现了相同的接口
 *              2、底层都是数组实现的
 *              3、初始默认长度都为10。
 *              4、扩容底层都是用System.arraycopy()实现的。
 *          不同点：
 *              1.Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe)，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此,ArrayList的性能比Vector好。
 *              2.当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%的大小，这样,ArrayList就有利于节约内存空间。
 *     7.ArrayList与迭代器模式：
 *          抽象聚合类Aggregate。在ArrayList的Iterator迭代器实现中，没有抽象聚合类。虽然它实现了AbstractList，实现了List，但它向外部提供的创建迭代器的方法iterator()是它自己的。
 *          具体聚合类ConcreteAggregate。在ArrayList的Iterator迭代器实现中，指的是ArrayList。
 *          抽象迭代器Iterator。在ArrayList的Iterator迭代器实现中，指的是Iterator接口。
 *          具体迭代器ConcreteIterator。在ArrayList中的Iterator迭代器实现中，指的是Itr。
 *          原文：https://blog.csdn.net/panweiwei1994/article/details/76946406
 *
 * @author: cww
 * @DateTime: 2019/4/28 16:53
 */

public class ArrayListTheory {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("s1");
        list.add("s2");
        list.add("s3");
        list.add("s5");
        list.add("s4");
        list.add("s6");
        list.set(1,"s2_1");
        System.out.println(list);
    }
}
